One of the latest advances in computer technology has been the development of parallel multiprocessor networks, consisting of many processing nodes interconnected in various topological configurations. The advantage of these configurations is that the processing nodes can execute instructions simultaneously, reducing the overall processing time for any program. However, in order to increase the efficiency of the overall system, information and data must be transferred efficiently throughout the whole network configuration. Therefore, the goal in designing such configurations is to obtain the best paths between all the processing nodes. This has resulted in increasingly complex network configurations.
To help increase the overall system performance, software system routines are implemented across the processing node configurations. These routing algorithms are designed to reduce data contention and imbalancing, and are responsible for moving data across the node configuration.
In order to develop routing routines for each configuration, each routing routine must be tested and analyzed. Processor node performance must be analyzed because the efficiency of a routing routine is reflected by individual node performance. The best measure of efficiency is the dynamic analysis of individual node performance during the actual execution of software programs.
Presently, analysis is done by static routines that accrue information while the system is executing. Then after the execution is completed these routines generate statistical tables with overall node performance.
Graphic representations can help make the network more understandable by helping the user visualize the structure. Generally, the network configuration is depicted as wire diagrams or graphs. That is, the processing nodes are represented as graph vertices, while arcs connecting the vertices represent the actual physical wires connecting the nodes. For example, a three dimensional cube would be represented with vertices at each corner and arcs connecting the vertices revealing the sides of the cube in a frame-like structure. However, even in a simple cube configuration, any two dimensional representation would prohibit the viewer from discerning which nodes are physically connected with each other. The most common technique employed in computer graphics is a direct mapping of the three dimensional structure by projecting the z-axis onto the two dimensional display. The resultant display would show many false intersecting lines between the vertices immediately facing the viewer. The intersecting lines in the two dimensional display that do not intersect at a processing node are called false crossings.
For example, in a three dimensional representation of a cubic toroidal configuration, many of the nodes and lines are in the interior of the cube. A two dimensional representation would flatten the cube and cause the interior nodes to appear as if they were on the exterior edge. The viewer could become confused because the lines connecting the interior vertices would intersect the lines that connect the exterior vertices, thus deceiving the viewer of its spatial orientation.
In addition, in toroidal networks, there are no "exterior edge" nodes in the system. Each individual node has the same number of connecting lines and nearest neighbor nodes. Actual drawings of the network would show arcs that wrap around the display, adding to the complexity and confusion. Therefore, when displaying such configurations on screen or on paper, representations in either two or three dimensions do not reveal these arcs. Users must remember that arcs connect vertices on the left side of the cube to the vertices on the right, and vertices in the front to the vertices in the back.
Another problem with the two dimensional representation is that labelling the nodes for dynamic performance and statistical analysis is nearly impossible. Since current methods of representation make it difficult to discriminate the interior vertices, adding a label to indicate node identification or performance would further the congestion and confusion of viewing the overall network.
Network performance is an important factor in network design research and development. Achieving higher computational throughput requires using efficient loading and routing routines. Dynamically analyzing individual node performance is imperative to properly address problems of data coherency resulting from data bottlenecking and load imbalance.
Very little has been done in the way of performance analysis through dynamic graphic visualization of three dimensional networks in two dimensions.
One previous approach was to selectively display portions of the graph or network. U.S. Pat. No. 5,515,487 describes a method of selectively pruning desired portions of a graph or plurality of graphs while retaining information concerning the nodal interconnections. This method also can delete or hide specified nodes to create a skeletal representation. This method does suffer some drawbacks. First, all false crossings are not eliminated. The number of false arc crossings would depend upon the size of the portion selected to be displayed. As a result, this method would only be effective when displaying a relatively small number of nodes; even then, there is no guarantee of eliminating crossings. In addition, this method requires that the user know ahead of time what areas of the graph to select. Analysis of the network on whole would be difficult.
Another approach is described in the article, "Dynamic Graphs for Network Visualization", by Richard A. Becker, et al. (Proceedings of the First IEEE Conference on Visualization, Visualization '90, pg. 93-6). This method would only draw the arcs whose corresponding vertex performance statistics fall above or below a predetermined threshold. However, false crossings in congested areas of the network would not be eliminated. The article further describes dynamic methods of identifying areas of a network and activating or deactivating specific nodes. Again, this does not address the problem of false arc crossings nor does it provide an efficient method of eliminating the visual congestion of the whole network.
The present invention eliminates false crossings in the above methods by displaying three dimensional networks that create a hyperbolic projection in two dimensions which eliminates all false crossings.